package com.cwj.algorithm.graph;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author chenwujie
 * @date 2020-12-22 14:36
 */
public class BreadthFirstSearch {
    private Graph graph;
    private boolean[] marked;
    private int count;
    private Deque<Integer> temp;

    public BreadthFirstSearch(Graph graph){
        this.graph = graph;
        marked = new boolean[graph.getV()];
        temp = new LinkedList<>();
    }

    public void bfs(int v){
        System.out.println(v);
        temp.push(v);
        marked[v] = true;

        while (!temp.isEmpty()){
            Integer poll = temp.poll();
            Deque<Integer> vertexes = graph.getVertexes(poll);
            for (Integer vertex : vertexes) {
                if(!marked(vertex)){
                    bfs(vertex);
                }
            }
        }
        count++;
    }

    public int getCount() {
        return count;
    }

    public boolean marked(int v){
        return marked[v];
    }
}
